#include <bits/stdc++.h>
using namespace std;
char s[1000000],t[1000000];

int n;
int main()
{
	cin >> n;
	while(n--)
	{
        int sx[26] = { 0 },tx[26] = { 0 };
		scanf("%s %s", s, t);
		for (int i = 0; i < strlen(s); i++)
		{
			sx[s[i] - 'a']++;
		}
		for (int i = 0; i < strlen(t); i++)
		{
			tx[t[i] - 'a']++;
		}
		int m = 100000;
		for (int i = 0; i < 26; i++)
		{
			if(tx[i] > 0)
				if (m > sx[i] / tx[i])
					m = sx[i] / tx[i];
		}
		cout << m  << endl;
	} 
	return 0;
}
